package algorithms.a02sortbasic;

import algorithms.utis.SortTestHelper;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author 王昊然
 * @create 2018-02-06 9:02
 **/
public class ShellSort {

    public static void sort(Comparable[] arr) {

        int n = arr.length;

        // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
        int h = 1;
        while (h < n / 3) h = 3 * h + 1;

        while (h >= 1) {

            // h-sort the array
            for (int i = h; i < n; i++) {

                // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
                Comparable e = arr[i];
                int j = i;
                for (; j >= h && e.compareTo(arr[j - h]) < 0; j -= h)
                    arr[j] = arr[j - h];
                arr[j] = e;
            }
            h /= 3;
        }
    }

    public static void main(String[] args) {

//        Integer[] arr = new Integer[]{20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
//        sort(arr);

        int N = 15000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 400000); //1排序数组数值范围小，插入排序优势明显
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);
        Integer[] arr4 = Arrays.copyOf(arr, arr.length);
        Integer[] arr5 = Arrays.copyOf(arr, arr.length);

        System.out.print("忽略--------");
        SortTestHelper.testSort(SelectionSort.class, arr, "sortWithMinAndMax");//testSort第一次计算比较慢，不作参考
        SortTestHelper.testSort(InsertionSort.class, arr);
        SortTestHelper.testSort(BubbleSort.class, arr, "sortAdvanced");
        SortTestHelper.testSort(ShellSort.class, arr);
        System.out.println("----------");

        SortTestHelper.testSort(SelectionSort.class, arr2, "sortWithMinAndMax");
        SortTestHelper.testSort(InsertionSort.class, arr3);
        SortTestHelper.testSort(BubbleSort.class, arr4, "sortAdvanced");
        SortTestHelper.testSort(ShellSort.class, arr5);
    }
}
